//编写一个程序，通过已填充的空格来解决数独问题。 
//
// 一个数独的解法需遵循如下规则： 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 
// 
//
// 空白格用 '.' 表示。 
//
// 
//
// 一个数独。 
//
// 
//
// 答案被标成红色。 
//
// Note: 
//
// 
// 给定的数独序列只包含数字 1-9 和字符 '.' 。 
// 你可以假设给定的数独只有唯一解。 
// 给定数独永远是 9x9 形式的。 
// 
// Related Topics 哈希表 回溯算法 
// 👍 505 👎 0

package leetcode.editor.cn;

//Java：解数独
public class P37SudokuSolver {

    /**
     * 思路： 回溯算法，保存递归现场以便回溯，然后递归方法也比较难写
     *
     * 执行用时： 5 ms , 在所有 Java 提交中击败了 69.26% 的用户 内存消耗： 36.8 MB , 在所有 Java 提交中击败了 96.17% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private char[] ch = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
        boolean[][] rows = new boolean[9][9];
        boolean[][] columns = new boolean[9][9];
        boolean[][] nineGrids = new boolean[9][9];

        public void solveSudoku(char[][] board) {
            // 找到第一个 为.的然后进入递归，之后循环就能退了
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] != '.') {
                        int index = board[i][j] - '1';
                        int k = getGridIndex(i, j);     // 第i宫格
                        rows[i][index] = true;
                        columns[j][index] = true;
                        nineGrids[k][index] = true;
                    }
                }
            }
            dfs(board, 0, 0);
        }

        private boolean dfs(char[][] board, int i, int j) {
            // 寻找空位,找不到返回true
            while (board[i][j] != '.') {
                j++;
                if (j >= 9) {
                    i++;
                    j = 0;
                }
                if (i >= 9) {
                    return true;
                }
            }

            for (int index = 0; index < ch.length; index++) {
                int k = getGridIndex(i, j);     // 第i宫格
                if (rows[i][index] || columns[j][index] || nineGrids[k][index]) {
                    continue;
                }

                board[i][j] = ch[index];
                rows[i][index] = true;
                columns[j][index] = true;
                nineGrids[k][index] = true;

                if (dfs(board, i, j)) {
                    // 都没有空位，成功
                    return true;
                } else {
                    // 失败，回溯
                    rows[i][index] = false;
                    columns[j][index] = false;
                    nineGrids[k][index] = false;
                    board[i][j] = '.';
                }
            }
            return false;

        }

        /**
         * 获取第几个九宫格  [0-8]
         * 0 1 2
         * 3 4 5
         * 6 7 8
         */
        private int getGridIndex(int i, int j) {
            int a = i / 3;
            int b = j / 3;
            return a * 3 + b;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        char[][] ch = new char[][] {
                {
                        '5', '3', '.', '.', '7', '.', '.', '.', '.'
                },
                {
                        '6', '.', '.', '1', '9', '5', '.', '.', '.'
                },
                {
                        '.', '9', '8', '.', '.', '.', '.', '6', '.'
                },
                {
                        '8', '.', '.', '.', '6', '.', '.', '.', '3'
                },
                {
                        '4', '.', '.', '8', '.', '3', '.', '.', '1'
                },
                {
                        '7', '.', '.', '.', '2', '.', '.', '.', '6'
                },
                {
                        '.', '6', '.', '.', '.', '.', '2', '8', '.'
                },
                {
                        '.', '.', '.', '4', '1', '9', '.', '.', '5'
                },
                {
                        '.', '.', '.', '.', '8', '.', '.', '7', '9'
                }
        };

        Solution solution = new P37SudokuSolver().new Solution();
        solution.solveSudoku(ch);
        System.out.println(ch.toString());
        // TO TEST
    }


}